// 给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

// 示例 1:

// 输入: [[1,1],[2,2],[3,3]]
// 输出: 3
// 解释:
// ^
// |
// |        o
// |     o
// |  o  
// +------------->
// 0  1  2  3  4
// 示例 2:

// 输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
// 输出: 4
// 解释:
// ^
// |
// |  o
// |     o        o
// |        o
// |  o        o
// +------------------->
// 0  1  2  3  4  5  6

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

// 双重循环，字典，斜率表示
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n < 3) return n;
        int res{0};
        for (int i{0}; i < n; ++i) {
            int duplicate{0};
            int curMax{0};
            unordered_map<string, int> lines{};

            for (int j{i+1}; j < n; ++j) {
                // 统计相同的点
                if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
                    duplicate += 1;
                    continue;
                }
                int diffX = points[j][0] - points[i][0];
                int diffY = points[j][1] - points[i][1];
                int temp = gcd(diffX, diffY);
                string key = to_string(diffX / temp) + "/" + to_string(diffY / temp); // 斜率
                ++lines[key];
                curMax = max(curMax, lines[key]);
            }
            res = max(res, curMax + duplicate + 1); // +1是因为lines[key]里面只加了两个点中的一个
        }
        return res;
    }
    // 最大公约数（Greatest Common Divisor）
    int gcd(const int& a, const int& b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
};